// 堆排序
// 堆
// parent (i - 1) / 2
// left 2i + 1
// right 2i + 2
function swap (arr, i, j) {
  [arr[i],arr[j]] = [arr[j],arr[i]]
}

// 将每个子二叉树调整为堆
function heapify (tree, n, i) {
  // 假设当前根节点最大
  let max = i
  let left = 2*i + 1
  let right = 2*i + 2
  
  // 越界不处理
  if (left < n && tree[left] > tree[max]) {
    max = left
  }
  // 越界不处理
  if (right < n && tree[right] > tree[max]) {
    max = right
  }

  // 找到了最大的节点,如果不是跟节点就交换位置,
  // 交换完对交换的节点也进行heapify
  if (max != i) {
    swap(tree, i, max)
    heapify(tree,n, max)
  }
}

// 构建堆
function buildHeap (tree, n) {
  let last_node = n - 1;
  let parent = Math.floor((last_node - 1) / 2)
  for (let i = parent; i >= 0 ; i--) {
    heapify(tree, n, i)    
  }
}

// 每次将堆顶的元素(最大的)放到最后一位,在对堆顶进行heapify,那么堆顶就又是最大的了.
// 重复上面的步骤,就能得到排序好的数组
function heap_sort (tree, n) {
  buildHeap(tree, n)
  for (let i = n - 1; i > 0; i--) {
    // 最后一个元素和堆顶交换
    swap(tree, i, 0)
    // 砍断剩下元素的最后一个元素
    // 也就是把当前最大的元素放到数组最后面,不改动了
    // 然后对剩下的元素继续构建堆
    heapify(tree, i, 0)
  }
}

let arr = [10,4,3,5,1]
heap_sort(arr, arr.length)
console.log(arr)